// 注意是连续子数组，和背包问题不一样
// 前缀和数组+哈希表
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sum(n + 1, 0);
        // unordered_set<int> rec;
        unordered_map<int, int> rec; //注意要存个数，可能加的不是一个
        // [1,-1,0]
        // 0
        int cnt = 0;
        rec[0] = 1; //注意！
        if (nums.empty()) return 0;
        for (int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + nums[i];
            if (rec.find(sum[i + 1] - k) != rec.end()) cnt += rec[sum[i + 1] - k];
            rec[sum[i + 1]]++;
            // if (rec.find(sum[i + 1] - k) != rec.end()) cnt++; //放后面k=0会出问题
        }
        return cnt;
    }
};